<HTML>
<HEAD>
   <TITLE>QDD : A Quantum Computer Emulation Library</TITLE>
<META NAME="keywords" CONTENT="quantum, quantum logic, quantum computer, binary decision diagram, BDD, QDD, quantum computer emulator, Shor, factoring, SHORNUF">
<META NAME="description" CONTENT="A C++ Quantum Computer Emulation Library">
</HEAD>
<BODY TEXT="#000000" LINK="#009696" BGCOLOR="#FFFFFF" VLINK="#006464" ALINK="#404040" BACKGROUND="images/qdd.gif">

<CENTER><FONT SIZE=+3>QDD : A Quantum Computer Emulation Library</FONT></CENTER>
<P>
<CENTER><FONT SIZE=+1>(and SHORNUF : An Implementation of Shor's Quantum Factoring Algorithm)</FONT></CENTER>
<P>
<CENTER>by : <a href="http://thegreves.com/david">David Greve</a></CENTER>

<P>
<HR WIDTH="100%">
<P>
<CENTER><FONT SIZE=+2>Overview</FONT></CENTER>
<P>

QDD is a C++ library which provides a relatively intuitive set of
quantum computing constructs within the context of the C++ programming
environment.  QDD is unique in that the its emulation of quantum
computing is based upon a Binary Decision Diagram 
<a href="http://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.ps">
(BDD) </a> representation of the quantum state.  This is in contrast
to the complex number representation used by <a
href="http://tph.tuwien.ac.at/~oemer/qc/qcl/"> QCL</a> and <a
href="http://www.openqubit.org/"> Open QuBit</a>.  Quantum Fog is
another quantum system simulation package developed by the <a
href="http://www.ar-tiste.com">Artiste </a> company.  Quantum Fog is
similar to QCL and Open QuBit in that it provides an exact simulation
of quantum behavior, but it differs in that it uses Bayesian Nets to
represent the quantum state.  Bayesian Nets are used in Quantum Fog
because of their expressivness and because they are considered a
natural vehicle for working with the conditional probabilities
typically encountered in entangled quantum states.  Where Bayesian
Nets are a natural vehicle for effectively expressing conditional
probabilities, BDDs are a natural vehicle for effectively describing
boolean functions.  The use of BDDs to model the underlying quantum
state allows QDD to model relatively large quantum states and provides
a relatively high degree of performance.  In the reference
implementation of Shor's factoring algorithm provided with the QDD
library, SHORNUF, QDD can factor a 16 bit number in approximately 8
minutes on a P200 with 64M of RAM.  However, the use of a BDD
representation also restricts QDD to operating as a "digital" quantum
computer.  <a href="http://tph.tuwien.ac.at/~oemer/qc/qcl/"> QCL</a>
and <a href="http://www.openqubit.org/"> Open QuBit</a>, in contrast,
support an "analog" computer model. Although the BDD representation
used by QDD provides a relatively high degree of scalability and
performance nearly linear in the size of the state representation, the
size of the underlying representation is still exponential in the
number of quantum bits used and therefore QDD still cannot be used to
efficiently factor very large numbers.  Nonetheless, it is hoped that,
by releasing the source code for QDD, others will be inspired to
consider other optimizations to the library that might lead to new or
better techniques for modeling quantum computation.

<P>
The QDD library is free software licensed under the <a
href="lgpl.html">LGPL</a> and the program SHORNUF is free software
licensed under the <a href="gpl.html">GPL</a>.

<P>
<HR WIDTH="100%">
<P>
<CENTER><FONT SIZE=+2>The Code</FONT></CENTER>
<P>

I make no claims at this point about the portability of this code.  I
have compiled it on a Sun Solaris machine and a RedHat 5.2 Linux
system (upgraded from 5.0).  However, I have noticed that the RedHat
5.2 systems (as shipped) don't include the g++ Integer class library
(why?) previously in the package libg++-devel.  For this reason, I
have included a pre-compiled i386 g++ library as an option as well.

<p>
<li><a href="http://thegreves.com/david/software/QDD.README">Download</a> the README.
<p>
<li><a href="http://thegreves.com/david/software/QDD.tar.gz">Download</a> the source.
<p>
<li><a href="http://thegreves.com/david/software/QDD-i386.tar.gz">Download</a> a pre-compiled i386 binary (w/g++ Integer library).
<p>
<li><a href="http://thegreves.com/david/software/QDD-i386-g++.tar.gz">Download</a> just the i386 g++ Integer library.

<p>
If you try QDD and find it useful or interesting, or if you find a
bug or have a suggestion, please let <a href="mailto:dagreve@iname.com"> me </a> know.

<P>
<HR WIDTH="100%">
<P>
<CENTER><FONT SIZE=+2>Documentation</FONT></CENTER>
<P>

The best I can do at this point is a couple of small, commented <a
href="example.html"> excerpts </a> from the SHORNUF program that
illustrate some high points of using QDD to implement quantum
operations.

<p>

Beyond that, the code <b>is</b> the documentation.  I may ultimately
publish a short paper on how BDDs are used by QDD to represent quantum
states.  However, in the absence of overwhelming demand, I will first
work on trying to find better graphical representations for quantum
states (Now, <b> that </b> would be something!).  For an excellent
overview of mixing classical and quantum computing concepts, see the
<a href="http://tph.tuwien.ac.at/~oemer/qc/qcl/"> QCL</a>
documentation by <a href="mailto:oemer@tph.tuwien.ac.at"> Bernhard
Oemer</a>.


<P>
<HR WIDTH="100%">
<P>
<CENTER><FONT SIZE=+2>Future Work</FONT></CENTER>
<P>

My ultimate goal for QDD is to use it to factor RSA <a
href="http://www.rsa.com/rsalabs/html/factoring.html"> challenge </a>
problems.  However, given the current capabilities of QDD, this would
really be quite an accomplishment!

<p>My primary focus in the coming months (years?) will be on the
fundamental representation used by QDD.  It is only through
breakthroughs in this area that QDD can ever hope to take on RSA
challenge problems.  In keeping with this philosophy, my future work
will involve :

<p><li> Improved BDD representation.  Do reversible AND-XOR functions
lend themselves to sub-exponential graphical representations?  I would 
like to think that they do! My first step in this direction will be to
explore the use of <a href="http://www.cs.cmu.edu/~bryant/pubdir/dac95.ps"
> *BMDs </a> .. they look very promising for this application!

<p><li> A more realistic FFT operation over quantum states represented
with BDDs.  The current implementation is a bit of a "cheat" since it
provides an exact measurement of periodicity.  Finding such an
operation might open the door to more analog-like operations on the
QDD state.  I have the feeling that it is possible if only I could
just wrap (warp) my mind around the problem.

<p>Aside from these tasks, there are lots of software engineering
types of things that could be done to it (better naming conventions,
more consistent interface, etc).  However, since I am not a software
engineer, these things will have to wait.

<p>If you would be interested in helping me to improve QDD in any way
(theory, coding, documentation, permanent home page, etc), feel free
to let me know.  Of course QDD is open source software, so you are
free to improve or extend it on your own in any way you see fit as
long as the result remains free.

<P>
<HR WIDTH="100%">
<P>
<CENTER><FONT SIZE=+2>Acknowledgements and References</FONT></CENTER>
<P>

<p>
The BDD package used by (and distributed with) QDD is the <a
href="http://britta.it.dtu.dk/~jl/buddy/"> BuDDy </a> package by 
<a href="mailto:jl@it.dtu.dk"> Jorn Lind-Nielsen </a>.

<p>
The seminal
<a href="http://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.ps">
paper </a> on BDDs was written by <a
href="mailto:Randy.Bryant@cs.cmu.edu"> Randy Bryant </a>. His paper
on <a href="http://www.cs.cmu.edu/~bryant/pubdir/dac95.ps"> *BMDs 
</a> also looks very promising for this application.

<p>
The quantum algorithms used in SHORNUF are taken almost directly from
those distributed with <a
href="http://tph.tuwien.ac.at/~oemer/qc/qcl/"> QCL</a>, by <a
href="mailto:oemer@tph.tuwien.ac.at"> Bernhard Oemer</a>.

<p>
Of course, Shor's factorization <a
href="http://www.research.att.com/~shor/papers/index.html"> algorithm
</a> came to us courtesy of <a
href="mailto:shor@research.att.com"> Peter Shor</a>.

<p>
Thanks to <a href="mailto:cowles@uwyo.edu"> John Cowles
</a> from the <a href="http://www.cs.uwyo.edu/~cowles/cowles.html">
University of Wyoming</a> for his assistance in understanding quantum
factorization, the properties of mod, and the super-cool modular
inverse function.

<p>
The <a href="http://www.openqubit.org/"> Open QuBit</a> project.

<p>
Computing with a cup of coffee : <a
href="http://www.media.mit.edu/physics/projects/spins/home.html"> Bulk
Spin </a>

<p>
<a href="http://www.qubit.org/"> QuBit.org </a>

<P>
<HR WIDTH="100%">
<P>

<CENTER>Contact <a href="mailto:TheBeaNerd@gmail.com">Dave Greve</a> or visit his <a href="http://thegreves.com/david/">home page</a></CENTER>

</BODY>
</HTML>
